package tree

//divideAndConquer 通过分治法实现DFS(深度优先搜索)
func divideAndConquer(root *Node) []int {
	result := make([]int, 0)
	//返回条件
	if root == nil {
		return result
	}

	//分治(Divide)
	left := divideAndConquer(root.Left)
	right := divideAndConquer(root.Right)

	//合并结果(Conquer)
	result = append(result, root.Val)
	result = append(result, left...)
	result = append(result, right...)
	return result
}

func DfsTraversalDivideAndConquer(root *Node) []int {
	result := divideAndConquer(root)
	return result
}
